#include "mazemodel.h"

#include <QRandomGenerator>
#include <QQueue>
#include <QSet>
#include <QMap>

MazeModel::MazeModel(int width, int height)
    : m_width(width)
    , m_height(height)
{
    int density = 40; //  block density %
    for(int i = width * height * density / 100; i; --i)
    {
        int x = QRandomGenerator::global()->bounded(width);
        int y = QRandomGenerator::global()->bounded(height);
        m_blocks.push_back({x, y});
    }
}

MazeModel::~MazeModel(){}

int MazeModel::width() const {return m_width;}

int MazeModel::height() const{return m_height;}

const QVector<QPoint>& MazeModel::blocks() const{return m_blocks;}

const QVector<QPoint> &MazeModel::path() const{return m_path;}

bool MazeModel::findPath(QPoint start, QPoint stop)
{
    m_path.clear();
    QSet<QPair<int, int>> blocked;
    for(auto &it : m_blocks) blocked.insert({it.x(), it.y()});

    if(blocked.contains({start.x(), start.y()})) return false;
    if(blocked.contains({stop.x(), stop.y()})) return false;

    QQueue<QVector<int>> qstep;
    QQueue<QMap<int, QPoint>> qpath;
    QMap<int, QPoint> map;
    map[1] = start;
    qpath.enqueue(map);
    qstep.enqueue({start.x(), start.y(), 1}); // push

    blocked.insert({start.x(), start.y()});

    while(!qstep.empty() and !qpath.empty())
    {
        int x = qstep.front().at(0);
        int y = qstep.front().at(1);
        int s = qstep.front().at(2); // step count

        auto map = qpath.front();

        if(x == stop.x() and y == stop.y())
        {
            for(auto &it : map) m_path.push_back(it);
            return true;
        }
        qstep.dequeue(); // pop
        qpath.dequeue();
        for(int x : {x - 1, x + 1} )
        {
            if(x < 0 or x > (width() - 1)) continue;
            if(blocked.contains({x, y})) continue;
            blocked.insert({x, y});
            map[s + 1] = QPoint(x, y);
            qpath.enqueue(map);
            qstep.enqueue({x, y, s + 1});
        }
        for(int y : {y - 1, y + 1} )
        {
            if(y < 0 or y > (height() - 1)) continue;
            if(blocked.contains({x, y})) continue;
            blocked.insert({x, y});
            map[s + 1] = QPoint(x, y);
            qpath.enqueue(map);
            qstep.enqueue({x, y, s + 1});
        }
    }
    return false;
}
